{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Collisions of Monkeys on a Polygon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: monkeyMove"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猴子碰撞的方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在有一个正凸多边形，其上共有 <code>n</code> 个顶点。顶点按顺时针方向从 <code>0</code> 到 <code>n - 1</code> 依次编号。每个顶点上 <strong>正好有一只猴子</strong> 。下图中是一个 6 个顶点的凸多边形。</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/22/hexagon.jpg\" style=\"width: 300px; height: 293px;\" /></p>\n",
    "\n",
    "<p>每个猴子同时移动到相邻的顶点。顶点 <code>i</code> 的相邻顶点可以是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>顺时针方向的顶点 <code>(i + 1) % n</code> ，或</li>\n",
    "\t<li>逆时针方向的顶点 <code>(i - 1 + n) % n</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果移动后至少有两只猴子停留在同一个顶点上或者相交在一条边上，则会发生 <strong>碰撞</strong> 。</p>\n",
    "\n",
    "<p>返回猴子至少发生 <strong>一次碰撞 </strong>的移动方法数。由于答案可能非常大，请返回对 <code>10<sup>9</sup>+7</code> 取余后的结果。</p>\n",
    "\n",
    "<p><strong>注意</strong>，每只猴子只能移动一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>共计 8 种移动方式。\n",
    "下面列出两种会发生碰撞的方式：\n",
    "- 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。\n",
    "- 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。\n",
    "可以证明，有 6 种让猴子碰撞的方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>可以证明，有 14 种让猴子碰撞的方法。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-collisions-of-monkeys-on-a-polygon](https://leetcode.cn/problems/count-collisions-of-monkeys-on-a-polygon/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-collisions-of-monkeys-on-a-polygon](https://leetcode.cn/problems/count-collisions-of-monkeys-on-a-polygon/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        def quick_pow(base, n, mod):\n",
    "            res = 1\n",
    "            while n:\n",
    "                if n&1:\n",
    "                    res = res*base % mod\n",
    "                n >>= 1\n",
    "                base = base*base % mod\n",
    "            return res\n",
    "        return (quick_pow(2, n, mod)-2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = pow(2, n, MOD) - 2\n",
    "        return MOD + res if res < 0 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        ans = 1\n",
    "        x = 2 \n",
    "        mod = 10 ** 9 + 7\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                ans = (ans * x) % mod\n",
    "            x = (x * x) % mod \n",
    "            n //= 2\n",
    "        return (ans - 2 + mod) % mod "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = int(1e9 + 7)\n",
    "        ans, base = 1, 2\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                ans = ans * base % mod\n",
    "            base = base * base % mod\n",
    "            n >>= 1\n",
    "        return (ans - 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (pow(2, n, mod) - 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2,n,MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        Mod = 10 ** 9 + 7;\n",
    "        return (pow(2, n, Mod) - 2) % Mod;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        m = 10 ** 9 + 7\n",
    "        return (pow(2,n,m)- 2) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        return (pow(2,n,mod) - 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (pow(2,n,mod)-2)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        return (pow(2,n,mod)-2+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        return (pow(2, n, MOD)-2)% MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return (pow(2,n,10**9+7)-2) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        res = 1\n",
    "        mod = 10**9+7\n",
    "        return (pow(2, n, mod) - 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (pow(2, n, mod) - 2) % mod;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (pow(2, n, mod) - 2) % mod;\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        dm = 10 ** 9 + 7\n",
    "        return (pow(2, n, dm) - 2) % dm\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return (pow(2, n, (10 ** 9 + 7)) - 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return (pow(2, n, 10 ** 9 + 7) - 2) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return 2 * (pow(2, n - 1, 10 ** 9 + 7) - 1) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (pow(2, n, mod) - 2 + mod) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        M = 10**9+7\n",
    "        def power2(x):\n",
    "            if not x: return 1\n",
    "            res = power2(x>>1) ** 2 % M\n",
    "            if x & 1:\n",
    "                res <<=1\n",
    "            return res % M\n",
    "        return (power2(n) - 2) % M\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return (pow(2,n,MOD)-2)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        def qpow(a, n, mod):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            elif n % 2 == 1:\n",
    "                return (qpow(a, n - 1, mod) * a) % mod\n",
    "            else:\n",
    "                return (qpow(a, n / 2, mod) ** 2) % mod\n",
    "        mod = 10 ** 9 + 7\n",
    "        return (qpow(2, n, mod) + mod - 2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def quickPower(n):\n",
    "            if(n == 0):\n",
    "                return 1\n",
    "            if(n == 1):\n",
    "                return 2\n",
    "            if(n in memo):\n",
    "                return memo[n]\n",
    "            p = 1\n",
    "            x = 2\n",
    "            while(2*p <= n):\n",
    "                x = x**2 % M\n",
    "                p *= 2\n",
    "            memo[n] = x * quickPower(n-p) % M\n",
    "            return memo[n]\n",
    "        return (quickPower(n)-2) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mul = 2\n",
    "        res = 1\n",
    "        mm = 10 ** 9 + 7\n",
    "        while n > 0:\n",
    "            if n & 1 == 1:\n",
    "                res *= mul\n",
    "                if res > mm:\n",
    "                    res %= mm\n",
    "                    \n",
    "            mul *= mul\n",
    "            n >>= 1\n",
    "            mul %= mm\n",
    "        \n",
    "        return (res - 2) % mm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        A=10**9+7\n",
    "        def pow(x,n):\n",
    "            s=bin(n)[2:]\n",
    "            dic={0:x}\n",
    "            for i in range(1,len(s)):\n",
    "                dic[i]=(dic[i-1]*dic[i-1])%A\n",
    "            ans=1\n",
    "            s=s[::-1]\n",
    "            for i in range(len(s)):\n",
    "                if s[i]=='1':\n",
    "                    ans=(ans*dic[i])%A\n",
    "            return ans\n",
    "        return (A+pow(2,n)-2)%A\n",
    "            \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return (pow(2, n, MOD) - 2) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def monkeyMove(self, n: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        return (pow(2, n, MOD) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def quickPower(n):\n",
    "            if(n == 0):\n",
    "                return 1\n",
    "            if(n == 1):\n",
    "                return 2\n",
    "            if(n in memo):\n",
    "                return memo[n]\n",
    "            p = 1\n",
    "            x = 2\n",
    "            while(2*p <= n):\n",
    "                x = x**2 % M\n",
    "                p *= 2\n",
    "            memo[n] = x * quickPower(n-p) % M\n",
    "            return memo[n]\n",
    "        return (quickPower(n)-2) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        mod = 1000000007\n",
    "        def qpow(x, y):\n",
    "            mod = 1000000007\n",
    "            if y == 0:\n",
    "                return 1\n",
    "            elif y == 1:\n",
    "                return x\n",
    "            elif y % 2 == 1:\n",
    "                return (qpow(x, y - 1) * x) % mod\n",
    "            elif y % 2 == 0:\n",
    "                a = (qpow(x, y // 2)) % mod\n",
    "                return a * a\n",
    "        \n",
    "        return (qpow(2, n) - 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10**9+7\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def quickPower(n):\n",
    "            if(n == 0):\n",
    "                return 1\n",
    "            if(n == 1):\n",
    "                return 2\n",
    "            if(n in memo):\n",
    "                return memo[n]\n",
    "            p = 1\n",
    "            x = 2\n",
    "            while(2*p <= n):\n",
    "                x = x**2 % M\n",
    "                p *= 2\n",
    "            memo[n] = x * quickPower(n-p)\n",
    "            return memo[n]\n",
    "        return (quickPower(n)-2) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "@cache\n",
    "def myPow(n, k):\n",
    "    if k == 1: return 2\n",
    "    if k % 2 == 0: return (myPow(n, k // 2) ** 2) % MOD\n",
    "    return (myPow(n, k - 1) * 2) % MOD\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        \n",
    "\n",
    "\n",
    "        return (myPow(2, n) - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return ((1 << n) - 2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        return ((1 << n) % MOD - 2) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return ((1 << n) - 2)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return ((1 << n) - 2) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def monkeyMove(self, n: int) -> int:\n",
    "        return ((1<<n)-2)%(10**9+7)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
